By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 25, Issue 2, pp. 235-476

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications

Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis

pp. 235-251

BibTeX  Abstract Full Text:  PDF

Robust Characterizations of Polynomials with Applications to Program Testing

Ronitt Rubinfeld and Madhu Sudan

pp. 252-271

BibTeX  Abstract Full Text:  PDF

Genome Rearrangements and Sorting by Reversals

Vineet Bafna and Pavel A. Pevzner

pp. 272-289

BibTeX  Abstract Full Text:  PDF

Note on: "A Linear-Time Algorithm for Computing $K$-Terminal Reliability in Series-Parallel Network"

A. Satyanarayana, R. K. Wood, L. Camarinopoulos, and G. Pampoukis

p. 290

BibTeX  Abstract Full Text:  PDF

Upward Planar Drawing of Single-Source Acyclic Digraphs

Michael D. Hutton and Anna Lubiw

pp. 291-311

BibTeX  Abstract Full Text:  PDF

An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem

Vijaya Ramachandran and Honghua Yang

pp. 312-339

BibTeX  Abstract Full Text:  PDF

The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection

Richard Chang and Jim Kadin

pp. 340-354

BibTeX  Abstract Full Text:  PDF

Low-Degree Spanning Trees of Small Weight

Samir Khuller, Balaji Raghavachari, and Neal Young

pp. 355-368

BibTeX  Abstract Full Text:  PDF

Optimal Clock Synchronization under Different Delay Assumptions

Hagit Attiya, Amir Herzberg, and Sergio Rajsbaum

pp. 369-389

BibTeX  Abstract Full Text:  PDF

Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs

Xiaotie Deng, Pavol Hell, and Jing Huang

pp. 390-403

BibTeX  Abstract Full Text:  PDF

An $O(N + M)$-Time Algorithm for Finding a Minimum-Weight Dominating Set in a Permutation Graph

C. Rhee, Y. D. Liang, S. K. Dhall, and S. Lakshmivarahan

pp. 404-419

BibTeX  Abstract Full Text:  PDF

Generalized Kraft's Inequality and Discrete $k$-Modal Search

Anmol Mathur and Edward M. Reingold

pp. 420-447

BibTeX  Abstract Full Text:  PDF

An Algebraic Model for Combinatorial Problems

Richard E. Stearns and Harry B. Hunt III

pp. 448-476

BibTeX  Abstract Full Text:  PDF